package algorithm.sort;

import java.util.Arrays;

public class mergeSort {


    public static void main(String[] args) {
        // 从小到大排序
        System.out.println("======推导========");
        deductionQuick();
        System.out.println("======准备数据========");
        int[] arr = TestHelp.random(10);
        TestHelp.print("比较前",arr);
        long begin = TestHelp.begin();
        mergeSort(arr,0,arr.length-1,new int[arr.length]);
        TestHelp.end(begin);
        TestHelp.print("比较后",arr);

    }

    /**
     * 归并排序 先分，后治，八分四，四分二，二分一，一合二，二合四，四合八，有序数组排序
     * 时间复杂度O(nlogn)
     * 空间复杂度O(n)，最多时需要一个临时数组存储
     * 稳定？？
     */
    public static void mergeSort(int[] arr,int begin,int end,int[] temp){
        if(begin >= end){
            return;
        }
        int middle = (begin+end)/2;
        mergeSort(arr,begin,middle,temp);
        mergeSort(arr,middle+1,end,temp);
        merge(arr,begin,middle,end,new int[arr.length]);
    }



    /**
     * 逐步推导，演绎
     */
    public static void deductionQuick(){
        int[] arr = new int[]{8,3,12,6,19,2,33,1,2,5};
        sort(arr,0,arr.length-1,new int[arr.length],0,0);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr,int begin,int end,int[] temp,int leftCounter,int rightCoounter){
        if(begin >= end){
            return;
        }
        int middle = (begin+end)/2;
        sort(arr,begin,middle,temp,leftCounter+1,rightCoounter);
        System.out.println("左递归："+leftCounter+" "+Arrays.toString(arr));
        sort(arr,middle+1,end,temp,leftCounter,rightCoounter+1);
        System.out.println("右递归："+rightCoounter+" "+Arrays.toString(arr));
        // 变成有序的数组，并合并
        merge(arr,begin,middle,end,temp);
    }

    public static void merge(int[] arr,int low,int middle,int high,int[] temp){
        // 定义指针 好像是两个数组相互比较
        int p1 = low;
        int p2 = middle+1;
        int i = low;
        // 指针在两个有序的数组上，交替移动，比较大小，小的存储到临时数组中
        while(p1<=middle && p2<=high){
            if(arr[p1] < arr[p2]){
                temp[i] = arr[p1];
                p1++;
                i++;
            }else{
                temp[i] = arr[p2];
                p2++;
                i++;
            }
        }
        // 有序数组后的所有元素，把所有指针都移完
        while(p1<=middle){
            temp[i] = arr[p1];
            p1++;
            i++;
        }
        while(p2<=high){
            temp[i] = arr[p2];
            p2++;
            i++;
        }
        // 复制到原有数组中
        for (int j = low; j <= high; j++) {
            arr[j] = temp[j];
        }
    }
}
